package A2019;

/*
 * 给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求
第 20190324 项的最后 4 位数字。//4659
 */
public class _2_数列求值 {

	public static void main(String[] args) {
	//	reslut();
		int[][] fa = { { 1, 1 }, { 1, 0 } };
		int[][] num=matrixPower(fa,2);
		for (int i = 0; i < num.length; i++) {
			for (int j = 0; j < num.length; j++) {
				System.out.print(num[i][j]+" ");
			}
			System.out.println();
		}
	}
	private static int[][] twoMatrixPlus(int[][] a,int[][] b) {
		int[][] ans=new int[a.length][b[0].length]; 
		for (int i = 0; i < ans.length; i++) {
			for (int j = 0; j < ans.length; j++) {
				ans[i][j]=0;
			}
		}
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < b[0].length; j++) {
				for (int j2 = 0; j2 < a[0].length; j2++) {
					ans[i][j]+=a[i][j2]*b[j2][j];
					ans[i][j]%=10000;
				}
			}
		}
		return ans;
	}
	private static int[][] matrixPower(int[][] a,int n) {
		int[][] ans=new int[a.length][a[0].length]; 
		for (int i = 0; i < ans.length; i++) {
			for (int j = 0; j < ans[0].length; j++) {
				if(i==j) {
					ans[i][j]=1;
				}else {
					ans[i][j]=0;
				}
			}
		}
		while(n!=0) {
			if((n&1)==1) {
				ans=twoMatrixPlus(ans,a);
			}
			a=twoMatrixPlus(a,a);
			n=n>>1;
		}
		return ans;
	}
	static void reslut() {
		int a=1,b=1,c=1;
		for (int i = 3; i < 20190324; i++) {//解法一
			int temp=(a+b+c)%10000;
			a=b;
			b=c;
			c=temp;
		}
		System.out.println(c);
	}
}
